//
// Created by 紫霄 on 2020/5/10.
//

#ifndef LEETCODE_32_3_H
#define LEETCODE_32_3_H
#include <deque>
#include <vector>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
  vector<vector<int>> ans;
  vector<vector<int>> levelOrder(TreeNode *root) {
    if (!root)
      return ans;
    vector<int> temp;
    deque<TreeNode *> curNodes;
    int levelCnt = 0;
    curNodes.emplace_back(root);
    dealLevel(curNodes, 1);
    return ans;
  }
  void dealLevel(deque<TreeNode *> curLevel, int LevelCnt) {
    deque<TreeNode *> nextLevel; //储存下一层节点
    vector<int> curNodes;        //储存当前层节点的值
    if (LevelCnt % 2) {          //假如当前层是奇数
      while (!curLevel.empty()) {
        auto temp = curLevel.front();
        if (temp->left)
          nextLevel.emplace_back(temp->left); //先左后右，从后插入
        if (temp->right)
          nextLevel.emplace_back(temp->right);
        curNodes.emplace_back(temp->val); //储存当前值；
        curLevel.pop_front();             //弹出头部
      }
    } else {
      while (!curLevel.empty()) {
        auto temp = curLevel.back();
        if (temp->right)
          nextLevel.emplace_front(temp->right); //先右后左，从前插入
        if (temp->left)
          nextLevel.emplace_front(temp->left);
        curNodes.emplace_back(temp->val);
        curLevel.pop_back();
      }
    }
    ans.emplace_back(curNodes); //添加到答案中
    if (!nextLevel.empty()) {
      dealLevel(nextLevel, LevelCnt + 1);
    }
  }
};
#endif // LEETCODE_32_3_H
